package Algorithm.sort.basic;

import utils.CommonUtils;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 基数排序：先获取数组中最大值的位数，然后从个位开始按每个数的个位数排序调整数组，使数组只看每个数的最后一位时是有序的，再按每个数的十位数排序调整数组，
 * 使数组只看每个数的最后两位时是有序的，一直到最大位数，此时数组就是有序的了。
 *
 * **性能**：时间复杂度为O(n * d)，d为待排序数组中最大值的位数。空间复杂度为O(n+m)，m为桶的数量。稳定
 *
 * **适用场景**：和快排相比，就在具体场景中看d和logn谁大了，一般来说在数据量较为巨大的场景表现会比较优秀，可以进行外排
 */
public class RadixSort {

    public static void main(String[] args) {
//        int[] A = new int[]{56,622,1,21,3333,69,9};
//        //注意，radixSort()并没有修改上面A的引用指向的数组，如果直接在这里打印A则还是原来的数组
//        System.out.println(Arrays.toString(radixSort2(A)));

        //通过下面的测试可以看到，当数据量巨大，而数据的最大值位数不大时，基数排序要优于快排
        //如果原始数据是链表的话差异会更加明显
        int[] A = CommonUtils.getRandomNums(10000000, 1000);
        int[] B = Arrays.copyOf(A,A.length);
        int[] C = Arrays.copyOf(A,A.length);
        long time = System.currentTimeMillis();

        QuickSort.quickSort(A, 0, A.length-1);
        long time1 = System.currentTimeMillis();
        System.out.println("快排耗时"+(time1-time));

        int[] x = radixSort(B);
        long time2 = System.currentTimeMillis();
        System.out.println("基数排序耗时"+(time2-time1));

        int[] y = radixSort2(C);
        long time3 = System.currentTimeMillis();
        System.out.println("基数排序耗时"+(time3-time2));
    }

    static int[] radixSort(int[] A) {
        int max=A[0];
        for (int i=1;i < A.length;i++) {
            if (max < A[i])
                max = A[i];
        }
        //求最大值的位数
        int temp = max, maxDigit=1;
        while (temp%10 != temp) {
            temp = temp/10;
            maxDigit++;
        }
        //初始化0~9号共10个桶
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10);
        for (int i=0;i < 10;i++)
            bucketList.add(new ArrayList<>());
        //从个位到最高位依次进行排序
        for(int i=1;i <= maxDigit;i++) {
            //根据每个数的i位数进行桶排序
            for (int j=0;j < A.length;j++) {
                //第i位数即数除以10^i的余数 再除以10^(i-1)得到的商
                int iNum = (A[j]%(int)Math.pow(10, i))/(int)Math.pow(10, i-1);
                //i位数值为多少就放到几号桶中
                bucketList.get(iNum).add(A[j]);
            }
            //将桶中的数依次取出
            A = bucketList.stream().flatMap(ArrayList::stream).mapToInt(Integer::valueOf).toArray();
            bucketList.forEach(ArrayList::clear);
        }
        return A;
    }

    //优化一下 使用两组桶 倒腾过来倒腾过去 减少取出的访存时间
    static int[] radixSort2(int[] A) {
        int max=A[0];
        for (int i=1;i < A.length;i++) {
            if (max < A[i])
                max = A[i];
        }
        //求最大值的位数
        int temp = max, maxDigit=1;
        while (temp%10 != temp) {
            temp = temp/10;
            maxDigit++;
        }
        //初始化0~9号共10个桶
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10);
        for (int i=0;i < 10;i++)
            bucketList.add(new ArrayList<>());
        ArrayList<ArrayList<Integer>> bucket2List = new ArrayList<>(10);
        for (int i=0;i < 10;i++)
            bucket2List.add(new ArrayList<>());
        //根据每个数的i位数进行桶排序
        int i = 1;
        for (int j=0;j < A.length;j++) {
            //第i位数即数除以10^i的余数 再除以10^(i-1)得到的商
            int iNum = (A[j]%(int)Math.pow(10, i))/(int)Math.pow(10, i-1);
            //i位数值为多少就放到几号桶中
            bucketList.get(iNum).add(A[j]);
        }
        boolean flag=true;
        for(i=2;i <= maxDigit;i++) {
            if (flag) {
                for (ArrayList<Integer> bucket : bucketList) {
                    for (Integer num : bucket) {
                        int iNum = (num%(int)Math.pow(10, i))/(int)Math.pow(10, i-1);
                        bucket2List.get(iNum).add(num);
                    }
                    bucket.clear();
                }
            } else {
                for (ArrayList<Integer> bucket : bucket2List) {
                    for (Integer num : bucket) {
                        int iNum = (num%(int)Math.pow(10, i))/(int)Math.pow(10, i-1);
                        bucketList.get(iNum).add(num);
                    }
                    bucket.clear();
                }
            }
            flag = !flag;
        }
        if (flag) {
            return bucketList.stream().flatMap(ArrayList::stream).mapToInt(Integer::valueOf).toArray();
        } else {
            return bucket2List.stream().flatMap(ArrayList::stream).mapToInt(Integer::valueOf).toArray();
        }
    }
}
